import java.security.KeyStore;
import java.util.*;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map  = new HashMap<>();
        int[] ret = new int[2];
        for(int i = 0; i<nums.length; i++) {
            int k = target - nums[i];
            if(map.containsKey(k)) {
                ret[0] = map.get(k);
                ret[1] = i;
                return ret;
            }
            map.put(nums[i],i);
        }
        return ret;
    }

    //判断是否互为字符重排
    public boolean CheckPermutation(String s1, String s2) {
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int[] hash = new int[26];
        for(char ch:str1) {
            hash[ch-'a']++;
        }
        for(char ch:str2) {
            hash[ch-'a']--;
        }
        for(int i = 0; i<26; i++) {
            if(hash[i] !=0) {
                return false;
            }
        }
        return true;
    }

    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> map = new HashSet<>();
        for(int x:nums) {
            if(map.contains(x)) {
                return true;
            }
            map.add(x);
        }
        return false;
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i<nums.length; i++) {
            if(map.containsKey(nums[i]) && Math.abs(map.get(nums[i]) - i) <= k) {
                return true;
            }
            map.put(nums[i],i);
        }
        return false;
    }

    public boolean Check(String s1, String s2) {
        if(s1.length() != s2.length()) return false;
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int[] hash = new int[26];
        for(char ch:str1) {
            hash[ch-'a']++;
        }
        for(char ch:str2) {
            hash[ch-'a']--;
        }
        for(int i = 0; i<26; i++) {
            if(hash[i] !=0) {
                return false;
            }
        }
        return true;
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String,List<String>> map = new HashMap<>();
        for(String str:strs) {
            char[] tmp = str.toCharArray();
            Arrays.sort(tmp);
            if(map.containsKey(Arrays.toString(tmp))) {
                map.get(Arrays.toString(tmp)).add(str);
            }else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(Arrays.toString(tmp),list);
            }
        }
        return new ArrayList<>(map.values());
    }

    public List<List<String>> groupAnagrams1(String[] strs) {
        List<List<String>> list = new ArrayList<>();
        for(String str:strs) {
            //查找需要存放的位置
            int flag = 0;
            for(int i = 0; i<list.size(); i++) {
                if(Check(list.get(i).get(0),str)) {
                    list.get(i).add(str);
                    flag = 1;
                    break;
                }
            }
            if (flag == 0) {
                List<String> tmp = new ArrayList<>();
                tmp.add(str);
                list.add(tmp);
            }
        }

        return list;
    }

}

public class Test {
    public static void main(String[] args) {

    }
}
